#include <string>
using std::string;
#include <iostream>
using std::cout;
#include <stdint.h>
uint32_t hash32(uint32_t key)
{
#if 0
	// thomas wang
	key += ~(key << 15);
	key ^= (key >> 10);
	key += key << 3;
	key ^= key >> 6;
	key += ~(key << 11);
	key ^= key >> 16;
	return key;
#endif

#if 1
	key += (key << 16);
	key ^= (key >> 17);
	key += (key << 4);
	key ^= (key >>10);
	key += (key << 7);
	key ^= (key >> 23); // was 23
	return key;
#else
	key += (key << 1);
	key ^= (key >> 1);
	key += (key << 1);
	key ^= (key >> 1);
	key += (key << 1);
	key ^= (key >> 1); // was 23
	return key;
#endif
}

uint32_t hashstr(const char* data, uint32_t len, uint32_t  initval)
{
	int i;
	const uint8_t* orig = (const uint8_t*) data;
	const uint32_t* d = (const uint32_t*) data;
	int leftover = len % 4;
	int chunks = len / 4;
	uint32_t h = hash32(initval+1);
	for (i = 0; i < chunks; ++i) h = hash32(h ^ *d++);
	if (leftover == 0) return h;
	orig += len - leftover;
	uint32_t tmp = 0;
	switch (leftover) {
	case 3: tmp = *orig++;
	case 2: tmp = tmp << 8 + *orig++;
	case 1: tmp = tmp << 8 + *orig;
	}
	return hash32(tmp ^ h);
}

#include <set>
using std::set;

#include <math.h>

int main() {
	srandom(time(0));
	set<uint32_t> hashset;
	uint32_t count = 1;
	int last = 0;
	int pow2 = 1;
	int exponent = 0;
	uint32_t data[12];
	uint32_t d =random();
	cout << "looking for collision with " << d;
	while (true) {
		cout << "trying exponent = " << exponent << "\n";
		for (int j =last; j < pow2; ++j) {
			for (int k = 0; k < 12; ++k) {
				data[k] = random();
				//d *= 21;
			}
			uint32_t h = hashstr((const char*) data, 48, 1);
			if (h == d) {
				cout << "collision at 2^" << log2(count) << "\n";
				return 0;
			}
			count++;
		}

		last = pow2;
		pow2 *= 2;
		exponent++;
	}
	return 0;
}
